#include <stdio.h>

#include "RaidConf.h"
#include "MapSector.h"

/*
 * Function to map a given Logical Device sector number to Physical 
 * sector <disk number, sector offset>.
 * This function is same as raid5_compute_sector() in Linux RAID code.
 * Input: conf 			= raid configuration
 *				r_sector 	= logical sector number
 * Output: s_info		= <disk number in RAID array, sector offset in disk>
 */

void raid456_find_phys(raid5_conf_t *conf, sector_t r_sector, sector_info_t *s_info)
{
	sector_t stripe, stripe2;
	sector_t chunk_number;
	unsigned int chunk_offset;
	int dd_idx, pd_idx, qd_idx;
	int algorithm = conf->algorithm;
	int sectors_per_chunk = conf->chunk_sectors;
	int raid_disks = conf->raid_disks;
	int data_disks = conf->data_disks;

	/*
	 * Compute the chunk number and the sector offset inside the chunk
	 */
	chunk_offset = sector_div(r_sector, sectors_per_chunk);
	chunk_number = r_sector;

	/*
	 * Compute the stripe number
	 */
	stripe = chunk_number;
	dd_idx = sector_div(stripe, data_disks);
	stripe2 = stripe;
	/*
	 * Select the parity disk based on the user selected algorithm.
	 */
	pd_idx = qd_idx = -1;
	switch(conf->level) {
		case 4:
			break;
	
		case 5:
			switch (algorithm) {
				case ALGORITHM_LEFT_ASYMMETRIC:
				pd_idx = data_disks - sector_div(stripe2, raid_disks);
			if (dd_idx >= pd_idx)
				dd_idx++;
			break;
		case ALGORITHM_RIGHT_ASYMMETRIC:
			pd_idx = sector_div(stripe2, raid_disks);
			if (dd_idx >= pd_idx)
				dd_idx++;
			break;
		case ALGORITHM_LEFT_SYMMETRIC:
			pd_idx = data_disks - sector_div(stripe2, raid_disks);
			dd_idx = (pd_idx + 1 + dd_idx) % raid_disks;
			break;
		case ALGORITHM_RIGHT_SYMMETRIC:
			pd_idx = sector_div(stripe2, raid_disks);
			dd_idx = (pd_idx + 1 + dd_idx) % raid_disks;
			break;
		case ALGORITHM_PARITY_0:
			pd_idx = 0;
			dd_idx++;
			break;
		case ALGORITHM_PARITY_N:
			pd_idx = data_disks;
			break;
		default:
			fprintf(stderr, "RevMap: Wrong Algorithm type for RAID Level:%d\n",conf->level);
		}
		break;
	
	case 6:
		switch (algorithm) {
		case ALGORITHM_LEFT_ASYMMETRIC:
			pd_idx = raid_disks - 1 - sector_div(stripe2, raid_disks);
			qd_idx = pd_idx + 1;
			if (pd_idx == raid_disks-1) {
					dd_idx++;	/* Q D D D P */
				qd_idx = 0;
			} else if (dd_idx >= pd_idx)
				dd_idx += 2; /* D D P Q D */
			break;
		case ALGORITHM_RIGHT_ASYMMETRIC:
			pd_idx = sector_div(stripe2, raid_disks);
			qd_idx = pd_idx + 1;
			if (pd_idx == raid_disks-1) {
				dd_idx++;	/* Q D D D P */
				qd_idx = 0;
			} else if (dd_idx >= pd_idx)
				dd_idx += 2; /* D D P Q D */
			break;
		case ALGORITHM_LEFT_SYMMETRIC:
			pd_idx = raid_disks - 1 - sector_div(stripe2, raid_disks);
			qd_idx = (pd_idx + 1) % raid_disks;
			dd_idx = (pd_idx + 2 + dd_idx) % raid_disks;
			break;
		case ALGORITHM_RIGHT_SYMMETRIC:
			pd_idx = sector_div(stripe2, raid_disks);
			qd_idx = (pd_idx + 1) % raid_disks;
			dd_idx = (pd_idx + 2 + dd_idx) % raid_disks;
			break;
		case ALGORITHM_PARITY_0:
			pd_idx = 0;
			qd_idx = 1;
			dd_idx += 2;
			break;
		case ALGORITHM_PARITY_N:
			pd_idx = data_disks;
			qd_idx = data_disks + 1;
			break;
		case ALGORITHM_ROTATING_ZERO_RESTART:
			/* Exactly the same as RIGHT_ASYMMETRIC, but or
			 * of blocks for computing Q is different.
			 */
			pd_idx = sector_div(stripe2, raid_disks);
			qd_idx = pd_idx + 1;
			if (pd_idx == raid_disks-1) {
				dd_idx++;	/* Q D D D P */
				qd_idx = 0;
			} else if (dd_idx >= pd_idx)
					dd_idx += 2; /* D D P Q D */
			break;
	
		case ALGORITHM_ROTATING_N_RESTART:
			/* Same a left_asymmetric, by first stripe is
			 * D D D P Q  rather than
			 * Q D D D P
			 */
			stripe2 += 1;
			pd_idx = raid_disks - 1 - sector_div(stripe2, raid_disks);
			qd_idx = pd_idx + 1;
			if (pd_idx == raid_disks-1) {
				dd_idx++;	/* Q D D D P */
				qd_idx = 0;
			} else if (dd_idx >= pd_idx)
				dd_idx += 2; /* D D P Q D */
			break;

		case ALGORITHM_ROTATING_N_CONTINUE:
			/* Same as left_symmetric but Q is before P */
			pd_idx = raid_disks - 1 - sector_div(stripe2, raid_disks);
			qd_idx = (pd_idx + raid_disks - 1) % raid_disks;
			dd_idx = (pd_idx + 1 + dd_idx) % raid_disks;
			break;

		case ALGORITHM_LEFT_ASYMMETRIC_6:
			/* RAID5 left_asymmetric, with Q on last device */
			pd_idx = data_disks - sector_div(stripe2, raid_disks-1);
			if (dd_idx >= pd_idx)
				dd_idx++;
			qd_idx = raid_disks - 1;
			break;

		case ALGORITHM_RIGHT_ASYMMETRIC_6:
			pd_idx = sector_div(stripe2, raid_disks-1);
			if (dd_idx >= pd_idx)
				dd_idx++;
			qd_idx = raid_disks - 1;
			break;

		case ALGORITHM_LEFT_SYMMETRIC_6:
			pd_idx = data_disks - sector_div(stripe2, raid_disks-1);
			dd_idx = (pd_idx + 1 + dd_idx) % (raid_disks-1);
			qd_idx = raid_disks - 1;
			break;

		case ALGORITHM_RIGHT_SYMMETRIC_6:
			pd_idx = sector_div(stripe2, raid_disks-1);
			dd_idx = (pd_idx + 1 + dd_idx) % (raid_disks-1);
			qd_idx = raid_disks - 1;
			break;

		case ALGORITHM_PARITY_0_6:
			pd_idx = 0;
			dd_idx++;
			qd_idx = raid_disks - 1;
			break;

		default:
			fprintf(stderr, "RevMap: Wrong Algorithm type for RAID Level:%d\n",conf->level);
		}
		break;
	}

	/*
	 * Finally, compute the new sector number
	 */
	s_info->sector = (sector_t)stripe * sectors_per_chunk + chunk_offset;
	s_info->disknum = dd_idx;
}

/*
 * This function is the reverse of raid456_find_phy().
 * It maps a given Physical sector <disk number, sector offset>
 * to a Logical Device sector number.
 * Input: conf 		= raid configuration
 *				s_info 	= <disk number in RAID array, sector offset in disk>
 * Return: logical sector number.
 */

sector_t raid456_find_virt(raid5_conf_t *conf, sector_info_t *s_info)
{
	sector_t stripe, stripe2;
	unsigned int chunk_offset;
	int pd_idx, qd_idx;
	int algorithm = conf->algorithm;
	int sectors_per_chunk = conf->chunk_sectors;
	int raid_disks = conf->raid_disks;
	int data_disks = conf->data_disks;
	int dd_idx = s_info->disknum;
	sector_t sector;

	/*
	 * Compute the chunk number and the sector offset inside the chunk
	 */
	chunk_offset = sector_div(s_info->sector, sectors_per_chunk);
	stripe = s_info->sector;
	stripe2 = stripe;

	pd_idx = qd_idx = -1;
	switch (conf->level) {
		case RAID4: 
			break;

		case RAID5:
			switch (algorithm) {
				case ALGORITHM_LEFT_ASYMMETRIC:
					pd_idx = data_disks - sector_div(stripe2, raid_disks);
					if (dd_idx > pd_idx)
						dd_idx--;
					break;
				case ALGORITHM_RIGHT_ASYMMETRIC:
					pd_idx = sector_div(stripe2, raid_disks);
					if (dd_idx > pd_idx)
						dd_idx--;
					break;
				case ALGORITHM_LEFT_SYMMETRIC:
					pd_idx = data_disks - sector_div(stripe2, raid_disks);
					dd_idx = (raid_disks + dd_idx - pd_idx - 1)%raid_disks;
					break;
				case ALGORITHM_RIGHT_SYMMETRIC:
					pd_idx = sector_div(stripe2, raid_disks);
					dd_idx = (raid_disks + dd_idx - pd_idx - 1)%raid_disks;
					break;
				case ALGORITHM_PARITY_0:  /* P D D D */
					dd_idx--;
					break;
				case ALGORITHM_PARITY_N: /* D D D P */
					break;

				default:
					fprintf(stderr, "RevMap: Wrong Algorithm type for RAID Level:%d\n",conf->level);
			}
			break;

		case RAID6:
			switch (algorithm) {
				case ALGORITHM_LEFT_ASYMMETRIC:
					pd_idx = raid_disks - 1 - sector_div(stripe2, raid_disks);
					if (pd_idx == raid_disks-1)
						dd_idx--;	/* Q D D D P */
					else if (dd_idx > pd_idx)
						dd_idx -= 2; /* D D P Q D */
					break;
	
			
				case ALGORITHM_RIGHT_ASYMMETRIC:
					pd_idx = sector_div(stripe2, raid_disks);
					if (pd_idx == raid_disks-1)
						dd_idx--;	/* Q D D D P */
					else if (dd_idx > pd_idx)
						dd_idx -= 2; /* D D P Q D */
					break;

				case ALGORITHM_LEFT_SYMMETRIC:
					pd_idx = raid_disks - 1 - sector_div(stripe2, raid_disks);
					dd_idx = (raid_disks + dd_idx - pd_idx - 2)%raid_disks;
					break;

				case ALGORITHM_RIGHT_SYMMETRIC:
					pd_idx = sector_div(stripe2, raid_disks);
					dd_idx = (raid_disks + dd_idx - pd_idx - 2)%raid_disks;
					break;

				case ALGORITHM_PARITY_0:  /* P Q D D D */
					dd_idx -= 2;
					break;
				
				case ALGORITHM_PARITY_N: /* D D D P Q */
					break;
			
				case ALGORITHM_ROTATING_ZERO_RESTART:
					/* Exactly the same as RIGHT_ASYMMETRIC, but or
			 		* of blocks for computing Q is different.
			 		*/
					pd_idx = sector_div(stripe2, raid_disks);
					if (pd_idx == raid_disks-1)
						dd_idx--;	/* Q D D D P */
					else if (dd_idx > pd_idx)
						dd_idx -= 2; /* D D P Q D */
					break;

				case ALGORITHM_ROTATING_N_RESTART:
					/* Same a left_asymmetric, by first stripe is
			 		* D D D P Q  rather than
			 		* Q D D D P
			 		*/
					stripe2 += 1;
					pd_idx = raid_disks - 1 - sector_div(stripe2, raid_disks);
					if (pd_idx == raid_disks-1)
						dd_idx--;	/* Q D D D P */
					else if (dd_idx > pd_idx)
						dd_idx -= 2; /* D D P Q D */
					break;
	
				case ALGORITHM_ROTATING_N_CONTINUE:
					stripe2 += 1;
					/* Same as left_symmetric but Q is before P */
					pd_idx = raid_disks - 1 - sector_div(stripe2, raid_disks);
					dd_idx = (raid_disks + dd_idx - pd_idx - 2)%raid_disks;
					break;
			
				case ALGORITHM_LEFT_ASYMMETRIC_6:
					/* RAID5 left_asymmetric, with Q on last device */
					pd_idx = data_disks - sector_div(stripe2, raid_disks-1);
					if (dd_idx > pd_idx)
						dd_idx--;
					break;

				case ALGORITHM_RIGHT_ASYMMETRIC_6:
					pd_idx = sector_div(stripe2, raid_disks-1);
					if (dd_idx > pd_idx)
						dd_idx--;
					break;

				case ALGORITHM_LEFT_SYMMETRIC_6:
					pd_idx = data_disks - sector_div(stripe2, raid_disks-1);
					dd_idx = (raid_disks -1 + dd_idx - pd_idx -1) % (raid_disks-1);
					break;

				case ALGORITHM_RIGHT_SYMMETRIC_6:
					pd_idx = sector_div(stripe2, raid_disks-1);
					dd_idx = (raid_disks -1 + dd_idx - pd_idx -1) % (raid_disks-1);
					break;

				case ALGORITHM_PARITY_0_6:
					dd_idx--;
					break;

				default:
					fprintf(stderr, "RevMap: Wrong Algorithm type for RAID Level:%d\n",conf->level);
			}
	}
	sector = stripe*data_disks*sectors_per_chunk + dd_idx*sectors_per_chunk + chunk_offset;
	return sector;
}

/*
 * This function is used to map a logical device sector number to Physical sector numbers
 * <raid disk number, sector number> in all the near/far copies of the raid10 array.
 * Input: conf = raid 10 configuration
 * 				r_sector = sector number in logical device.
 * Return: *s_info = pointer to <raid disk #, sector #> tuples.
 */

void raid10_find_phys(raid10_conf_t *conf, sector_t r_sector, r10_sector_info_t *s_info) 
{
	int n,f;
	sector_t sector;
	sector_t chunk;
	sector_t stripe;
	int dev;

	int slot = 0;

  /* Compute the chunk number and the sector offset inside the chunk */
	chunk = r_sector >> conf->chunk_shift;
	sector = r_sector & conf->chunk_mask;

	chunk *= conf->near_copies;
	stripe = chunk;
	dev = sector_div(stripe, conf->raid_disks);
	if (conf->far_offset)
		stripe *= conf->far_copies;

	sector += stripe << conf->chunk_shift;

	/* and calculate all the others */
	for (n=0; n < conf->near_copies; n++) {
		int d = dev;
		sector_t s = sector;
		s_info->devs[slot].sector = sector;
		s_info->devs[slot].disknum = d;
		slot++;

		for (f = 1; f < conf->far_copies; f++) {
			d += conf->near_copies;
			if (d >= conf->raid_disks)
				d -= conf->raid_disks;
			s += conf->stride;
			s_info->devs[slot].disknum = d;
			s_info->devs[slot].sector = s;
			slot++;
		}
		dev++;
		if (dev >= conf->raid_disks) {
			dev = 0;
			sector += (conf->chunk_mask + 1);
		}
	}
	if(slot != conf->copies)
		fprintf(stderr, "RevMap: error in RAID10 configuration\n");
}

/*
 * This function is the reverse of raid10_fuind_phy().
 * This function maps the Physical sector number <disk number, sector offset>
 * in a raid10 array to the logical device sector number. 
 */

sector_t raid10_find_virt(raid10_conf_t *conf, sector_info_t *s_info)
{
	sector_t offset, chunk, vchunk;
	sector_t sector = s_info->sector;
	int dev = s_info->disknum;

	offset = sector & conf->chunk_mask;
	if (conf->far_offset) {
		int fc;
		chunk = sector >> conf->chunk_shift;
		fc = sector_div(chunk, conf->far_copies);
		dev -= fc * conf->near_copies;
		if (dev < 0)
			dev += conf->raid_disks;
	} else {
		while (sector >= conf->stride) {
			sector -= conf->stride;
			if (dev < conf->near_copies)
				dev += conf->raid_disks - conf->near_copies;
			else
				dev -= conf->near_copies;
		}
		chunk = sector >> conf->chunk_shift;
	}
	vchunk = chunk * conf->raid_disks + dev;
	sector_div(vchunk, conf->near_copies);
	return (vchunk << conf->chunk_shift) + offset;
}


